package my.jwds.p2055;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PlatesBetweenCandles {

    public static void main(String[] args) {
        PlatesBetweenCandles obj = new PlatesBetweenCandles();
        String s = "***|**|*****|**||**|*";
        int [][] queries = JSON.parseObject("[[1,17],[4,5],[14,17],[5,11],[15,16]]",int[][].class);
        long start = System.currentTimeMillis();
        int [] res = obj.platesBetweenCandles1(s,queries);
        System.out.println("运行时间:"+(System.currentTimeMillis() - start));
        System.out.println(Arrays.toString(res));
    }

    public int[] platesBetweenCandles(String s, int[][] queries) {
        int l = s.length();
        int [] dp = new int[l];
        int pre = 0;
        boolean start = s.charAt(0) == '|';
        List<Integer> tokens = new ArrayList<>();
        if (start)tokens.add(0);
        for (int i = 1; i < l; i++) {
            if (s.charAt(i) == '*'){
                pre++;
            }else{
                if (start){
                    dp[i] = pre;
                }else{
                    start = true;
                }
                pre = 0;
                tokens.add(i);
            }
            dp[i] += dp[i-1];
        }

        int[]res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] tokenIndex = search(tokens,queries[i][0],queries[i][1]);
            res[i] =dp[tokenIndex[1]] - dp[tokenIndex[0]] ;
        }
        return  res;
    }

    private int[] search(List<Integer> tokens,int start,int end){
        int lower = 0,upper = tokens.size() -1;
        int res[] = new int[2];
        while(lower <= upper){
            int mid = (upper + lower)/2;
            int token = tokens.get(mid);
            if (token > start){
                res[0] = token;
                upper = mid-1;
            }else if (token < start){
                lower = mid+1;
            }else{
                res[0] = token;
                break;
            }
        }
        lower = 0;
        upper = tokens.size() -1;
        while(lower <= upper){
            int mid = (upper + lower)/2;
            int token = tokens.get(mid);
            if (token > end){
                upper = mid-1;
            }else if (token < end){
                res[1] = token;
                lower = mid+1;
            }else{
                res[1] = token;
                break;
            }
        }
        for (int i = 0; i < res.length; i++) {
            if (!(res[i] >= start && res[i] <= end))res[i] = 0;
        }
        return res;
    }


    public int[] platesBetweenCandles1(String s, int[][] queries) {
        int l = s.length(),pre = 0;
        int [] dp = new int[l];
        boolean start = s.charAt(0) == '|';
        int[]left = new int[l],right = new int[l];
        int prev = 0;
        for (int i = 1; i < l; i++) {
            if (s.charAt(i) == '*'){
                pre++;
            }else{
                if (start){
                    dp[i] = pre;
                }else{
                    start = true;
                }
                pre = 0;
                prev = i;
            }
            left[i] = prev;
            dp[i] += dp[i-1];
        }
        for (int i = l-1; i >= 0; i--) {
            if (s.charAt(i) == '|')prev = i;
            right[i] = prev;
        }

        int[]res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            if (left[queries[i][1]] > right[queries[i][0]]){
                res[i] =dp[left[queries[i][1]]] - dp[right[queries[i][0]]] ;
            }

        }
        return  res;
    }



}